package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.TreeNode;
import org.apache.commons.lang3.StringUtils;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @ClassName Medium_102_LevelOrderBinaryTree
 * @Description 更优的方法：https://leetcode.cn/problems/binary-tree-level-order-traversal/solution/yun-xing-shi-jian-0msshen-sou-yan-sou-by-crv8/
 * @Author wanghaiwei
 * @Date 2023/3/29 17:33
 */
public class Medium_102_LevelOrderBinaryTree {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.left == null && root.right == null) {
            result.add(Arrays.asList(root.val));
            return result;
        }
        List<TreeNode> levelNodes = new ArrayList<>();
        levelNodes.add(root);
        while (!levelNodes.isEmpty()) {
            List<TreeNode> tmp = new ArrayList<>();
            result.add(levelNodes.stream().map(t -> t.val).collect(Collectors.toList()));
            for (TreeNode node : levelNodes) {
                if (node.left != null) {
                    tmp.add(node.left);
                }
                if (node.right != null) {
                    tmp.add(node.right);
                }
            }
            levelNodes = tmp;
        }
        return result;
    }

    public static void main(String[] args) {
        Medium_102_LevelOrderBinaryTree solution = new Medium_102_LevelOrderBinaryTree();
        List<List<Integer>> results = solution.levelOrder(new TreeNode(new Integer[]{3, 9, 20, null, null, 15, 7}));
        System.out.printf("Input: root = [3,9,20,null,null,15,7]\nOutput: %s\n", results.stream().map(r -> "[" + StringUtils.join(r, ',') + "]").collect(Collectors.joining(",")));

        results = solution.levelOrder(new TreeNode(new Integer[]{1}));
        System.out.printf("Input: root = [1]\nOutput: %s\n", results.stream().map(r -> "[" + StringUtils.join(r, ',') + "]").collect(Collectors.joining(",")));

        results = solution.levelOrder(new TreeNode());
        System.out.printf("Input: root = []\nOutput: %s\n", results.stream().map(r -> "[" + StringUtils.join(r, ',') + "]").collect(Collectors.joining(",")));
    }
}
